/*
 * @lc app=leetcode.cn id=739 lang=typescript
 *
 * [739] 每日温度
 */

// @lc code=start

//  思路：单调栈
//  栈内存储index以便计算差值
//  参考：https://labuladong.github.io/algo/2/18/43/

//  复杂度：O(n) O(1)

function dailyTemperatures(temperatures: number[]): number[] {
    const res: number[] = []
    const stack: number[] = []
    for (let i = temperatures.length - 1; i >= 0; i--) {
        while (stack.length && temperatures[stack[stack.length - 1]] <= temperatures[i]) {
            stack.pop()
        }
        res[i] = stack.length ? (stack[stack.length - 1] - i) : 0
        stack.push(i)
    }
    return res
};
// @lc code=end

console.log(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))
// [1,1,4,2,1,1,0,0]
console.log(dailyTemperatures([30, 40, 50, 60]))  // [1,1,1,0]      

